package SlideWindows;

import java.util.Random;

public class L727_最小窗口子序列 {
    /**
     * 给定字符串S和T，在S中寻找最小子串W，使得T是W的子序列。  顺序必须一致，这个跟上面的题还不一样。
     * 这题跟 76是不一样的!!  76不要求顺序，这个要求顺序。。
     * S = "abcdebdde", T = "bde"
     * Output: "bcde"
     */
    public String minWindow(String S, String T) {
        String minWin = "";
        int j = 0;
        int minLen = S.length() + 1;
        for (int i = 0; i < S.length(); i++) {
            //这个很巧妙，两个指针指a、b， 有相等的j++，没有就i++. 这时候，j表示的是已经匹配了几个字符串
            if (S.charAt(i) == T.charAt(j)) {
                j++;
            }
            //已经都匹配上了，我们找到滑动窗口最右边了，这时候要开始在这里面找最小的了
            if (j == T.length()) {
                int end = i + 1;//end 表示最右边，下面代码都是要找最左边
                j--;
                while (j >= 0) {
                    //反着来，相等的话j--,同时这里相当于要把最左边给找出来
                    if (T.charAt(j) == S.charAt(i)) {
                        j--;
                    }
                    //经过上面的操作，i最开始是在窗口的最右边
                    i--;
                }
                //跟已经取到的结果做对比，取最小的
                if (end - i + 1 < minLen) {
                    minLen = end - i + 1;
                    minWin = S.substring(i + 1, end);
                }
                //i 和 j都已经回退到窗口最左边，这时候要 ++，开始新一轮的比对
                j++;
                i++;
            }
        }

        return minWin;
    }

    public static void main(String[] args){
        Random a = new Random();
        a.nextInt();
        System.out.println(Math.random());
        L727_最小窗口子序列 l = new L727_最小窗口子序列();
        l.minWindow("abcdebdde", "bde");
    }
}
